It is commonly recognized that electrical characteristics of transistors and interconnects are not the same for different chips and even for the same chip at different time moments or chip locations. Variation of electrical characteristics can be due to variation of process parameters, changing of environmental conditions and even chips aging (Hot Carriers Injections, Negative Bias Temperature Instability, electromigration, and so forth). Variation of electrical characteristics results in variations of gate timing characteristics. The traditional conservative way to handle these variations is to consider so-called process corners at which the gates have the worst combinations of delays. Then chips are designed so that they can properly function at all process corners assuming that as a result they will function at any other combination of gate delays.
Unfortunately, with decreasing transistor size and interconnect width, the variation of electrical characteristics is getting proportionally larger. Therefore, the approach to design for process corners, which used to work well, now results in too conservative and non-optimal designs because most design efforts and chip resources are spent to make chips function at very low-probability combinations of electrical characteristics.
An alternative approach to designing chips as described above is to consider actual statistical characteristics of process parameter variations and use them to compute statistical characteristics of a designed circuit. For digital circuits, this approach is known as statistical timing analysis. There are several varieties of statistical timing analysis.
One of the most useful for circuit analysis and optimization is parameterized statistical static timing analysis (STA). According to this technique, gate delays and signal arrival times are represented as functions of process parameters.A=f(X1, X2, . . . )  (1)
All the parameters are assumed independent. This assumption significantly simplifies the analysis but does not limit its applicability because independence can be obtained by a principal component analysis technique. Using this representation, the parameterized STA computes a statistical approximation of the circuit timing characteristics (arrival and required arrival times, delay, timing slack) as functions of the same parameters.
The process parameters can be considered as either globally correlated or fully random. Both types of parameters exhibit variation due to the manufacturing process. The correlated parameters have the same values for all gates and wires of the analyzed circuit while the fully random parameters vary for each gate independently. Usually, it is convenient to combine all the fully random parameters into one term.
The parameterized statistical STA can be either path-based or block-based. Path-based statistical STA analyzes each signal propagation path separately and computes the probability distribution for circuit delay as the probabilistic maximum of all paths delays. Usually this requires enumeration of all signal propagation paths and integration in the space of parameters variations, which is an inefficient computational procedure.
A more efficient technique of parameterized STA is so-called block-based statistical STA. This technique is very similar to traditional deterministic STA. It computes signal arrival times (or signal required arrival times) as functions of process parameters for each circuit node in their topological order similarly to propagating arrival times by a deterministic STA. It is convenient for both implementation and application. That kind of statistical timing analyzer can be easily implemented on the base of existing deterministic timing analyzer. This type of timing analysis lends itself to incremental operation, whereby after a change of the circuit is made, timing can be queried efficiently.
For computational efficiency, parameterized statistical block-based STA assumes that all parameters variations have normal Gaussian distributions and that gate and wire delays depend on parameters linearly. Without loss of generality, Gaussian distributions with 0 mean and unit standard deviation are assumed. This assumption allows representation of gate delays in first-order canonical form, as described by C. Visweswariah in U.S. patent application Ser. No. 10/666,353, entitled “System and Method for Statistical Timing Analysis of Digital Circuits”, filed on Sep. 19, 2003, incorporated herein by reference in its entirety (hereinafter referred to as the “System and Method for Statistical Timing Analysis of Digital Circuits patent”):
                    A        =                              a            0                    +                                    ∑                              i                =                1                            n                        ⁢                                                            a                  i                                ·                Δ                            ⁢                                                          ⁢                              X                i                                              +                                    a                              n                +                1                                      ⁢            Δ            ⁢                                                  ⁢                          R              a                                                          (        2        )            where: ao is a mean value; ΔXi is a variation of parameter Xi,
ΔXi=Xi−xo where x0 is the mean value of Xi; ai is the sensitivity of the gate delay to parameter variation ΔXi; ΔRa is a random variable responsible for uncorrelated variation of the gate delay; and an+1 is a sensitivity of the gate delay to uncorrelated variation ΔRa. The following United States Patent Applications, commonly assigned to the assignee herein, are incorporated by reference herein in their entireties: U.S. patent application Ser. No. 10/665,092, entitled “System and Method for Incremental Statistical Timing Analysis of Digital Circuits”, filed on Sep. 18, 2003; U.S. patent application Ser. No. 10/666,353, entitled “System and Method for Statistical Timing Analysis of Digital Circuits”, filed on Sep. 19, 2003; and U.S. patent application Ser. No. 10/666,470, entitled “System and Method for Probabilistic Criticality Prediction of Digital Circuits”, filed on Sep. 19, 2003.
Sensitivity coefficients express dependency of a gate delay on a process parameter. The last coefficient expresses a fully random part of delay variation. Using unit Gaussian but not arbitrary Gaussian distributions simplifies the analysis but is not restrictive because parameter distributions can always be normalized, e.g., by accumulating their non-zero means into delay means and properly adjusting sensitivity coefficients.
Block-based STA computes arrival times at each circuit node using two basic operations: incrementing arrival time by a gate delay and computing worst-case arrival time. The incrementing of the arrival time by a gate delay corresponds to propagating signals from a gate input to its output. This operation is performed by summation of the arrival time at the gate input and gate delay. The computing of the worst-case arrival time selects the worst-case signal from the signals arriving at a gate's inputs. The worst signal can be the latest or the earliest one depending on the type of timing analysis. The computing of the worst-case arrival time is performed by computing the maximum or the minimum of several arrival times. Herein, only the case of computing the latest arrival time is discussed. However, it is to be appreciated that the proposed approach can be easily extended to computation of the earliest arrival time using obvious symmetry between minimum and maximum functions, while maintaining the spirit of the present invention.
In deterministic timing analysis, these basic operations are trivial. In the statistical case, the situation is more complex because expressions, and not simply numbers, are operated upon.
Using the first-order canonical form of gate delays and applying some approximation, it is possible to compute signal arrival times at circuit nodes and circuit delay in the same linear canonical form. Incrementing an arrival time by a gate delay given in the first-order canonical form Equation 2 is known. Incrementing the arrival time is performed by summing the corresponding sensitivity coefficients, as described in the System and Method for Statistical Timing Analysis of Digital Circuits patent and, thus, it is not considered herein.
The computation of the maximum of the two arrival times represented in the first-order form Equation 2 is significantly more difficult because the maximum is a non-linear function. Therefore, parameterized statistical STA computes an approximate first-order representation of the maximum of the two arrival times.
Linear and Gaussian assumptions are very convenient for statistical parameterized STA because it is possible to use approximate analytical formulae for computing canonical forms of arrival times. Analytical formulae make statistical timing analysis fast and computationally efficient, which is important for implementing a statistical approach in circuit synthesis and optimization. Unfortunately, process parameters may have probability distributions, which are significantly different from Gaussian. It is impossible to approximate certain asymmetric distributions by Gaussian ones with a reasonable error. For example, via resistance distributions are asymmetric. Another problem arises from the fact that some parameters can affect delay in a non-linear way. Usually a linear approximation is justified by assuming that process parameter variation and the corresponding delay variation is sufficiently small. However, with the reduction of transistor sizes, process variation is getting higher. Therefore, a linear approximation of delay dependence on variation is not always sufficiently accurate. For example, delay of a gate depends on transistor channel length non-linearly.
Accordingly, it would be desirable and highly advantageous to have a system and method for accommodating non-Gaussian and nonlinear sources of variation in statistical static timing analysis.